package 经典排序算法;

import java.util.Scanner;

/**
 * @ClassName : 希尔排序
 * @Author : 骆发茂
 * @Date: 2021/3/4 19:16
 * @Description :
 */
public class 希尔排序_分割成特定增量的子序列_在进行插入排序 {
    public static void main(String[] args) {
        System.out.println("请输入一个串数字，以空格作为分割，我将为你排序");
        System.out.println("=================================");
        Scanner scanner = new Scanner(System.in);
        String strings = scanner.nextLine();
        String[] newstrings = strings.split(" ");
        int[] array = new int[newstrings.length];
        for (int i = 0; i < newstrings.length; i++) {
            array[i] = Integer.parseInt(newstrings[i]);
        }
        System.out.println("==========原数组排序前为：===============");
        for (int j : array) {
            System.out.print(j + "  ");
        }
        System.out.println();
        System.out.println("==========数组排序后为：===============");
        ShellSort(array);
        for (int j : array) {
            System.out.print(j + "  ");
        }
        System.out.println();

    }

    public static int[] ShellSort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex = preIndex - gap;
                }
                array[preIndex + gap] = temp;
            }

            gap = gap / 2;
        }
        return array;
    }
}
